package two.chapter_1.c1_5;

public class WeightedQuickFindUF extends UF {
    private int[] sz;

    public WeightedQuickFindUF(int N) {
        super(N);
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            sz[i] = 1;
        }
    }

    /**
     * p   q   0   1  2  3   4   5    6   7    8   9
     * -----------------------------------------------
     * 4   3   0   1  2  3   3   5    6   7    8   9
     * <p>
     * 3   8   0   1  2  3   3   5    6   7    3   9
     * <p>
     * 6   5   0   1  2  3   3   5    5   7    3   9
     * <p>
     * 9   4   0   1  2  3   3   5    5   7    3   3
     * <p>
     * 2   1   0   1  1  3   3   5    5   7    3   3
     * <p>
     * 8   9   0   1  1  3   3   5    5   7    3   3
     * <p>
     * 5   0   5   1  1  3   3   5    5   7    3   3
     * <p>
     * <p>
     * 加权的quickfind无非就是少了几次复制操作，比较操作一次都没有少，还增加了sz数组
     *
     * @param p
     * @param q
     */
    @Override
    public void union(int p, int q) {
        int pId = find(p);
        int qId = find(q);
        if (pId != qId) {
            int larger;
            int smaller;
            if (sz[pId] > sz[qId]) {
                larger = pId;
                smaller = qId;
                sz[pId] += sz[qId];
            } else {
                larger = qId;
                smaller = pId;
                sz[qId] += sz[pId];
            }

            for (int i = 0; i < ids.length; i++) {

                if (ids[i] == smaller) {
                    ids[i] = larger;

                }

            }
        }
    }

    @Override
    public int find(int p) {
        return ids[p];
    }
}
